package com.star.niuke;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;

/**
 * @author: liminghui
 * @date: 2021/7/22 10:36
 * @version: 1.0
 * @description: NC93 设计LRU缓存结构
 */
public class LRU2 {

    public static void main(String[] args) {
        LRU2 lru = new LRU2();

        int[][] operators = {{1, 1, 1}, {1, 2, 2}, {1, 3, 2}, {2, 1}, {1, 4, 4}, {2, 2}};
        int k = 3;
        int[] result = lru.LRU(operators, k);

        System.out.println(Arrays.toString(result));
    }

    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k         int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU(int[][] operators, int k) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        LRUCache lru = new LRUCache(k);
        for (int[] opt : operators) {
            if (opt[0] == 1) {
                lru.put(opt[1], opt[2]);
            } else {
                list.add(lru.get(opt[1]));
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for (int val : list) {
            res[i] = list.get(i);
            i++;
        }
        return res;
    }


    //设置LRU缓存结构
    class LRUCache {
        int cap;
        LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

        public LRUCache(int capactity) {
            this.cap = capactity;
        }

        // 将key变为最近使用
        private void makeRecently(int key) {
            int val = cache.get(key);
            //删除key，重新插入到队尾
            cache.remove(key);
            cache.put(key, val);
        }


        //获取值
        public int get(int key) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            //将这个key变为最近使用的
            makeRecently(key);
            return cache.get(key);
        }

        //存进值
        public void put(int key, int val) {
            if (cache.containsKey(key)) {
                cache.put(key, val);
                //设置为最近使用
                makeRecently(key);
                return;
            }

            //超出缓存的大小
            if (cache.size() >= this.cap) {
                //拿到链表头部的key（其最久未使用的key）
                int oldstKet = cache.keySet().iterator().next();
                cache.remove(oldstKet);
            }
            //将新的key添加到链表尾部
            cache.put(key, val);
        }
    }
}


